Grokking Microsoft Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Microsoft Easy Problems
Buddy Strings (easy)
Solution: Buddy Strings
Can Place Flowers (easy)
Solution: Can Place Flowers
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Maximum Number of Balloons (easy)
Solution: Maximum Number of Balloons
Binary Tree Path Sum (easy)
Solution: Binary Tree Path Sum
Pair with Target Sum (easy)
Solution: Pair with Target Sum
Buy Two Chocolates (easy)
Solution: Buy Two Chocolates
Root Equals Sum of Children (easy)
Solution: Root Equals Sum of Children
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Min Cost Climbing Stairs (easy)
Solution: Min Cost Climbing Stairs
Plus One (easy)
Solution: Plus One
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Find the Index of the First Occurrence in a String (easy)
Solution: Find the Index of the First Occurrence in a String
Merge Two Sorted Lists (easy)
Solution: Merge Two Sorted Lists
Nth Digit (medium)
Solution: Nth Digit
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Find Original Array From Doubled Array (medium)
Solution: Find Original Array From Doubled Array
Reverse Words in a String II (medium)
Solution: Reverse Words in a String II
Longest Arithmetic Subsequence (medium)
Solution: Longest Arithmetic Subsequence
Matchsticks to Square (medium)
Solution: Matchsticks to Square
Score of Parentheses (medium)
Solution: Score of Parentheses
Maximum Length of a Concatenated String with Unique Characters (medium)
Solution: Maximum Length of a Concatenated String with Unique Characters
Inorder Successor in BST (medium)
Solution: Inorder Successor in BST
Distribute Coins in Binary Tree (medium)
Solution: Distribute Coins in Binary Tree
Spiral Matrix (medium)
Solution: Spiral Matrix
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Sum of Subarray Minimums (medium)
Solution: Sum of Subarray Minimums
Rotate Image (medium)
Solution: Rotate Image
Combinations (medium)
Solution: Combinations
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Multiply Strings (medium)
Solution: Multiply Strings
Best Time to Buy and Sell Stock II (medium)
Solution: Best Time to Buy and Sell Stock II
Largest Palindromic Number (medium)
Solution: Largest Palindromic Number
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Next Permutation (medium)
Solution: Next Permutation
132 Pattern (medium)
Solution: 132 Pattern
Valid Sudoku (medium)
Solution: Valid Sudoku
Number of Islands (medium)
Solution: Number of Islands
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Solution: Buddy Strings

Problem Statement

Given two strings a and b, return true if they can be considered "buddy strings". Otherwise, return false.

Two strings are buddy strings if you can swap any two letters in one string to make it equal to the other string.

Examples

  • Example 1:

    • Input: a = "xy", b = "yx"
    • Expected Output: true
    • Justification: Swapping 'x' and 'y' in string a results in "yx", which matches string b.
  • Example 2:

    • Input: a = "ab", b = "cd"
    • Expected Output: false
    • Justification: There are differences at every position, and swapping any characters in a cannot make it equal to b.
  • Example 3:

    • Input: a = "abcde", b = "acbde"
    • Expected Output: true
    • Justification: Swapping 'b' and 'c' in string a results in "acbde", which matches string b. So, both strings are buddy strings.

Solution

To solve this problem, we start by comparing the lengths of the two strings. If their lengths differ, they cannot be buddy strings. For strings of equal length, we track the positions where they differ. If there are no differences and the first string has at least one repeating character, it means a swap could occur within the string to make it its own buddy string. If there are exactly two differences, we check if swapping the characters at these positions in one string makes the two strings equal. This approach ensures we accurately identify buddy strings by addressing both scenarios where strings are initially equal or need a specific swap to become equal.

Our approach is effective because it minimizes the number of checks needed to determine if two strings are buddy strings. By first checking the length, then the positions of difference, and finally the conditions for being buddy strings, we efficiently narrow down the possibilities with minimal computational overhead. This method balances thoroughness with efficiency, making it suitable for a wide range of inputs.

Step-by-step Algorithm

  1. Initial Length Check:

    • If a.length is not equal to b.length, return false immediately, as strings of different lengths cannot be buddy strings.
  2. Handle Identical Strings:

    • If the strings a and b are identical, then for them to be buddy strings, there must be at least one character in a that appears more than once. Use a frequency count array or a set to check for repeating characters. If a repeat is found, return true.
  3. Identify and Record Differences:

    • If a and b are not identical, iterate through both strings simultaneously to compare characters at each position.
    • Record the indices where a and b differ. Use two variables, first and second, initialized to -1, to store these indices.
    • If more than two differences are found, return false as a swap cannot resolve more than two differences.
  4. Check for Exactly Two Differences:

    • After identifying the indices of differences, check if swapping the characters at these positions in a would make it equal to b. This means that the character at first index in a should match the character at second index in b and vice versa.
  5. Final Verification:

    • If the conditions in step 4 are satisfied, return true, indicating that the strings are buddy strings by a single swap.
    • Otherwise, return false.

Algorithm Walkthrough

Consider the input a = "abcde", b = "acbde".

  1. Initial Length Check:

    • Both strings a and b are of the same length. This check passes, allowing us to proceed to the next step.
  2. Handle Identical Strings:

    • The strings a and b are not identical, so we move to the next step. There's no need to check for repeating characters since the strings differ.
  3. Identify and Record Differences:

    • As we iterate through both strings from the beginning, they match at the first position. At the second position, we encounter a difference ('b' in a vs 'c' in b), so we record first = 1.
    • Continuing, we find another difference at the third position ('c' in a vs 'b' in b), so we record second = 2. The rest of the characters match in both strings.
    • There are exactly two differences, and no more, which is what we need for a potential swap to make a and b equal.
  4. Check for Exactly Two Differences:

    • With first = 1 and second = 2, we check if swapping the characters at these positions in a would make it equal to b. Specifically, we're looking to see if after the swap, a[first] equals b[second] and a[second] equals b[first].
    • Before the swap: a = "abcde", b = "acbde"
    • After a hypothetical swap in a (swapping 'b' and 'c'): a would become "acbde".
    • This swapped version of a matches b exactly.
  5. Final Verification:

    • Since swapping 'b' and 'c' in a makes it identical to b, the strings are buddy strings. Therefore, we return true.
Image

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity: where n is the length of the strings, as the algorithm iterates over the strings at most once.
  • Space Complexity: for checking differences and in the worst case when the strings are identical to store character frequencies. However, because the character set is limited (assuming ASCII), this can also be considered in practical scenarios where the alphabet size is fixed.
Buddy Strings (easy)
Can Place Flowers (easy)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis